レインボーテーブル – パスワード流出への対策を根本から理解する。

はじめに

先日、Yahooに不正アクセスがあり、ユーザ名とパスワードを抽出しようとするプログラムが見つかったそうです。
そんな事もありまして、今回は少し趣を変えて、レインボーテーブルのお話をしたいと思います。
今まで概念は知っていても使う事がなかった技術ですが、この機会に詳しく知っておくのも良いかと思います。

レインボーテーブルは、ハッシュから平文を得るためのアルゴリズムの一つですが、実際にそのアルゴリズムで使用されるテーブルの事をいうこともあります。
今回はレインボーテーブルというアルゴリズムについて掘り下げて行きたいと思います。

ハッシュと平文のセットのテーブル

レインボーテーブルの基本的な考え方は、非常にシンプルで、このハッシュだったら平文はこれですよというのを事前に用意しておきましょうという事です。
例えば人気パスワードランキング2012より、上位5件のパスワードに付いてもしこのハッシュだったらこの平文です。というのをテーブルにしてみました。

ハッシュ(md5)	平文
5f4dcc3b5aa765d61d8327deb882cf99	password
e10adc3949ba59abbe56e057f20f883e	12346
25d55ad283aa400af464c76d713c07ad	12345678
e99a18c428cb38d5f260853678922e03	abc123
d8578edf8458ce06fbc5bb76a58c5ca4	qwerty

どれも一度は見たことがあるものばかりですね。abc123がこんな上位だとは思いませんでしたが、、

これはハッシュ値と、平文のセットを持ったテーブルです。
もし、ハッシュが「5f4dcc3b5aa765d61d8327deb882cf99」であった場合、
一発でパスワードが[password]であることがわかってしまいます。
これを様々な文字列を総当りでやって事前にデータ化しておこうというのが発端になっています。

簡単にパスワードを割り出す事が出来るのではありますが、データ量が膨大になってしまいます。
プレーンなテキストだったとしても、平文が[a-zA-Z0-9]62の文字種で8文字(限定)の組み合わせだったとしても全部で62^8通りもの組み合わせが作れます。

データのサイズもテラとか、ペタとかそれなりに大きくなります。
ハッシュの作り方もMD5,SHAなど色々あるので、それにあったものを作る必要があり、現実的ではありません。
ちなみにこれはレインボーテーブルではないんです。

テーブルの効率化

先ほどのような単純な対比表みたいなものだと使い物になるか怪しいくらいのデータ量になってしまいます。
そこで考えだされたのがレインボーテーブルです。
レインボーテーブル自体はデータ構造はシンプルですが、直接答えが書いてあるわけではないので、1対1の表に比べると解析に時間はかかります。
まずはレインボーテーブルの作り方を説明します。
説明の前に2つの関数を紹介させて下さい。

ハッシュ関数[以降 H()と表します。] hash = H(plain)

平文からハッシュ値を求める関数です。MD5やSHA1などがよく使われます。

還元関数[以降 R()と表します。] plain = R(hash,index)

ハッシュ関数とは逆にハッシュ値から平文を作り出す関数です。引数が同じであれば、必ず同じ平文が取り出せる必要があります。今回2つ目の引数にindexと置いているのは,もしhashが同じでもindexの値が異なっていれば、別の平文を生成するためです。こうすることで、重複を減らす事ができれば、同じデータ量のテーブルでも解析の成功率をあげる事ができます。

この2つの関数を使ってテーブルをどう効率化していくのかというのを順を追って見ていきます。

まず平文に対してH()でハッシュ値を生成します。
今度はそのハッシュ値にたいしてR()でもう一度平文を生成
次に今生成した平文に対してH()でハッシュ値を生成します
といったようにこれを何回も繰り返します。
何回か繰り返して、最後にR()で生成した平文と一番最初の平文、この2つのみ保存します。この2つの間にはいくつかの平文とハッシュ値がありますが、全部捨ててしまいます。ものすごく効率化できました。
これをチェインと呼びます。
大事な単語です。チェインです。

このチェインを色々な平文からスタートしてやっていく事で、レインボーテーブルを作ります。

この最初と最後だけがあれば、途中はいらないというのがレインボーテーブルのすごいところです。 この繰り返しを1000回やったとしても、最初と最後の平文以外必要無いのです。 1000回の中で出てきた平文とハッシュ値の組み合わせは、最初の平文があれば同じ手順を踏むことで求める事ができるからです。

いざ復元

復元の手順はテーブル作成よりも複雑です。
まず手に入れたハッシュ値を還元関数を使って平文を作ります。
この時の還元関数はテーブルを作った時と同じ物を使います。
もう一つ、チェインの末尾の平文を作る為に使った還元関数である必要もあります。 なので、ここで求まる平文Xは R(手に入れたハッシュ値,チェインの長さ);となります。
求めた平文Xとチェインの末尾の平文が同じチェインを探します。

もしここで発見出来る事が出来たなら、そのチェインの中入れたハッシュの元の平文が含まれている事になります。
そのチェインの先頭からまた同じ手順でチェインを作って行きます。
その過程で手に入れたハッシュ値と同じハッシュ値が出てきます（この段階で末尾の平文と合致するものがある時は末尾一個手前の平文が求めるべき平文の時です。）ので、

もし、末尾に合致するものが無かった場合は、手に入れたハッシュ値から還元関数で求めた平文からもう一度ハッシュ値を求め、さらに還元関数で平文を求めます。その平文がチェインの末尾にあるか調べます。 チェインの末尾に無い場合は任意の回数これを繰り返します。
繰り返しは最大でもチェインの長さになります。

先ほどの図とくらべて見て貰うとわかりますが、答えをチェインの後ろから前に向かって検索していっています。
表で言う縦一列を、末尾と合致するかどうかという方法のみで一発で照合してしまうので、チェインの数が増えたとしても非常に効率的です。

実際に実装してみたものをこのエントリの最後に載せておきますので、興味のある方は見てみて下さい。

他の方法とくらべて

ここまでレインボーテーブルの動きを追って来ましたが、他の方法とくらべるとどうなんでしょうか。
ここで比較するものとしては、BruteForce,平文:ハッシュのテーブルの2つとくらべて見ます。
おおまかにポジショニングマップを書くとこんな感じになります。実際は、解析時間、ストレージ量の小から大にかけては、天文学的な数値の差があります。でもイメージとしてはこんな感じです。

BruteForceは解析の時に総当りするので、解析時間はものすごく多い代わりに、事前にデータを必要としません。そしていつか必ず当たります。何万年後かはわかりませんが、、
平文：ハッシュのテーブルを事前に生成する方法は、解析時間はほぼ0に等しくする事も可能ですが、莫大なストレージを必要とします。テラ、ペタ、その次の次の次なんだっけ？っていうのを調べるのが面倒な位ストレージを必要とします。また、解析時間はかからないのですが、事前の計算量もものすごい事になります。
以上を踏まえて表にまとめると

	解析時間	ストレージ	事前処理時間
BruteForce	超大	無	無
平文:ハッシュ	極小	超大	大
レインボーテーブル	大	大	大

このような感じじゃないでしょうか。
超大が無いので、他に比べて現実的かなというイメージでいいと思います。

レインボーテーブルに対する対策

レインボーテーブルの説明だけするのも、あれなので、対策的なものも。
現在Free Rainbow Tablesでは様々なハッシュ値が公開されています。全部を圧縮した状態で約9T（2013年4月3日現在）あるので、利用できる人はそこまでいないとは思いますが、全く手がでない大きさというわけでもありません。解凍する環境もないので、解凍後のサイズはわかりませんが、、、

このブログを見ている人はおそらくWeb制作などのシステムを作る方たちが多いと思います。
パスワードを平文のままデータベースに保存するなんて事はしていないとは思います。おそらくハッシュ値をデータベースに保存していることでしょう。
MD5などでのハッシュが多いのでしょうか。

ここにもう一手間加えるだけで、レインボーテーブルを非効率化することができます。
saltをつけることです。そこそこ長い文字数の（出来れば合計26文字以上になるように）saltをつけて上げてください。もしくは、日本人なら日本語をsaltに含めるなど、free rainbow tableで公開されていない範囲のコードを使うのもひとつの手だと思います。そこまで計算するにはまだまだ時間もかかるはずです。
salt自身を推測されづらくするために、システム固定の文字列とたとえばユーザ名や、ユーザのIDなどユーザ固有のものを付け加えるのも非常に良いと思います。
開発者じゃなかったとしても、自分の使うパスワードを26文字以上にするなどすると、しばらくの間はパスワードのハッシュが流出しても解析されることは無いでしょう。きっと。。

さいごに

レインボーテーブルを使って何かをするということはあまりないかもしれませんが、レインボーテーブルという物もあるんだという事を頭に入れておいて貰えれば、きっとどこかで役に経つかもしれません。もしどこかに登録する時は、レインボーテーブルというものがあるんだという事を分かってパスワードを作ると、パスワード流出なんてなった時にも、レインボーテーブルじゃ解析出来ないんだっていうのは、少しだけ安心することが出来ると思います。

おまけ(Amazon S3を使った実装)

Amazon S3を使って試しに作ってみたソースがこちらです。 レインボーテーブルのデータをAmazon S3に置くのは非常に良いと思いますが、事前にハッシュを求めなくては行けないという性質上、ハッシュ計算の得意なGPUインスタンスをウン百台と使ってガリガリやらないと、使い物になるようなまともなレインボーテーブルは作成出来ませんのでご注意下さい。

public class RainbowTable {

MessageDigest md5; static final String S3_PREFIX = "MD5/"; static final String BUCKET_NAME = "BUCKET_NAME"; AmazonS3Client s3;

public RainbowTable() throws NoSuchAlgorithmException { this.md5 = MessageDigest.getInstance("MD5"); this.s3 = new AmazonS3Client(); }

public void createRainbowTable(int chainLength, int chainNum) { File tempFile = null; try { tempFile = File.createTempFile("1bytefile", ".t"); FileOutputStream s = new FileOutputStream(tempFile); s.write(1); s.close(); String p = "password"; for (int i = 0; i < chainNum; i++) { String last = this.createChain(p, chainLength); // 末尾の平文をkey, 先頭の平文をmetadataに保存 this.upload(last, tempFile, p); p = last; } } catch (IOException e1) { e1.printStackTrace(); } } public void upload(String key, File file, String headtext) { // file は1バイトのtempFile PutObjectRequest putObjectRequest = new PutObjectRequest(BUCKET_NAME, S3_PREFIX + key, file); ObjectMetadata om = new ObjectMetadata(); Map metadata = new HashMap(); // S3まともに使ったら高いから metadataを使う。 metadata.put("headplaintext", headtext); om.setUserMetadata(metadata); putObjectRequest.setMetadata(om); putObjectRequest.setStorageClass(StorageClass.ReducedRedundancy); putObjectRequest.setAccessControlList(new AccessControlList()); s3.putObject(putObjectRequest); }

public String check(String seed, String source) { String plain = seed; byte[] hash; for (int i = 0; i < 100; i++) { hash = this.hash(plain); if (source.equals(this.hash2HEX(hash))) { return plain; } plain = this.reverce(hash, i); } return null; } public String createChain(String seed, int length) { String plain = seed; byte[] hash; for (int i = 0; i < length; i++) { hash = this.hash(plain); plain = this.reverce(hash, i); } System.out.println(); return plain; } public String hash2HEX(byte[] sorce) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < sorce.length; i++) { int b = (0xFF & sorce[i]); if (b < 16) sb.append("0"); sb.append(Integer.toHexString(b)); } return sb.toString(); } public byte[] hash(String source) { return this.md5.digest(source.getBytes()); } public String reverce(byte[] hash, int i) { i = 0; StringBuffer sb = new StringBuffer(); for (byte h : hash) { int k = (h & 0xFF) + i; int a = (k % 26); a += 0x30; if (a > 0x39 && a < 0x41) { continue; } char c = (char) a; sb.append(c); } return sb.toString(); } private byte[] hexString2byteArray(String hex) { byte[] bytes = new byte[hex.length() / 2]; for (int index = 0; index < bytes.length; index++) { bytes[index] = (byte) Integer.parseInt( hex.substring(index * 2, (index + 1) * 2), 16); } return bytes; } public String crack(String hash, int chainLength) { String p = this.reverce(hexString2byteArray(hash), 0); S3Object obj = null; int counter = chainLength; do { try { obj = this.s3.getObject(BUCKET_NAME, S3_PREFIX + p); if (obj != null) { Map meta = obj.getObjectMetadata() .getUserMetadata(); String seed = meta.get("headplaintext"); if (seed != null && seed != "") { String password = this.check(seed, hash); if (password != null) { return password; } } } } catch (AmazonS3Exception e) { } if (counter < chainLength / 2) { break; } p = this.reverce(this.hash(p), counter--); } while (obj == null); return null; } } [/java] [java] RainbowTable rt = new RainbowTable(); // レインボーテーブルの作成 rt.createRainbowTable(4000, 1000000); [/java] [java] RainbowTable rt = new RainbowTable(); // ハッシュから平文を求める rt.crack("2cdc5f0037347498e5aea30c03ce65f7",4000); [/java]